合併排序法(Merge Sort)原理是會先將原始資料分割成兩個資料列，接著再將兩個資料繼續分割成兩個資料列，依此類推，直到無法再分割，也就是每組都只剩下一筆資料時，再兩兩合併各組資料，合併時也會進行該組排序，每次排序都是比較最左邊的資料，將較小的資料加到新的資料列中，依此類推，直到最後合併成一個排序好的資料列為止。

下面利用30 10 40 70 50 90 60 20由小到大排序。

時間複雜度 = 分割步驟數 + 合併步驟數

分割：分割含有 n 個資料需要 n-1 次，O(n)。
合併：合併的兩邊共用 n 個元素，每次都是比較最左邊的資料，將較小的加到新陣列中，因此每次排序與合併必須經過 n 次，每回合log n次，O(log n)。

平均時間複雜度為: O(n log n)

JavaScript

let data = [8,6,1,10,5,3,9,2,7,4]

function merge(left, right){
  let result = [];

  while (left.length&&right.length){
    //左右兩陣列第一個元素進行比較，較小的推入result
    if (left[0] < right[0]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }
  
  //while迴圈跳出時，表示左右陣列其中一個為空，因此左右判斷concat哪邊
  result = left.length ? result.concat(left) : result.concat(right)

  return result;
}

function mergeSort(array){

  if(array.length < 2){
    return array;
  }

  let mid = Math.floor(array.length/2);
  let leftArray = array.slice(0, mid);
  let rightArray = array.slice(mid, array.length);
  
  //用遞迴一直切到最後一個元素再合併
  return merge(mergeSort(leftArray), mergeSort(rightArray))
}

console.log(mergeSort(data))//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Python

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def merge(left, right):
    result = []

    while len(left) and len(right):
        if (left[0] < right[0]):
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    result = result+left if len(left) else result+right
    return result

def mergeSort(array):
    if len(array) < 2:
        return array

    mid = len(array)//2
    leftArray = array[:mid]
    rightArray = array[mid:]

    return merge(mergeSort(leftArray),mergeSort(rightArray))

print(mergeSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]